package warthog.parsegen;

import warthog.cradle.JavaClass;

public class CompressedTable {
	static class CompressedArray {
		int d;
		int[] locs;
		int[] acts;
		int exCount;
		int size, trim;
		public CompressedArray(Integer[] row, int d) {
			size=row.length;
			this.d = d; //;
			exCount = 0;
			for (Integer i:row) {
				if (i == null || i == d) continue;
				exCount++;
			}
			locs = new int[exCount];
			acts = new int[exCount];
			int k=0;
			for (int j=0; j<row.length; j++) {
				Integer i=row[j];
				if (i == null) continue;
				trim = j;
				if (i == d) continue;
				acts[k] = i;
				locs[k] = j;
				k++;
			}
			trim++;
		}
		public CompressedArray trim() {
			if (locs.length == 0) size=0;
			else size=locs[locs.length-1]+1;
			return this;
		}
	}
	int[] yyTable;
	int[] yyOffset;
	int[] yyCheck;
	int[] yyDefault;
	private int size;
	private int stateCount;
	public CompressedTable(int stateCount, int nontermCount) {
		yyTable = new int[0];
		yyCheck = new int[0];
		size=0;
		yyDefault = new int[stateCount+nontermCount];
		yyOffset = new int[stateCount+nontermCount];
		this.stateCount = stateCount;
	}
	public void addActionRow(int stateID, Integer[] row) {
		if (stateID >= stateCount) throw new IllegalArgumentException();
		install(stateID, new CompressedArray(row, defaultReduce(row)));
	}
	public void addGotoColumn(int nontermID, Integer[] col) {
		CompressedArray ca = new CompressedArray(col, defaultGoto(col));
		ca.size = ca.trim;
		install(stateCount+nontermID, ca);
	}
	private void install(int id, CompressedArray cr) {
		yyDefault[id] = cr.d;
		int at = yyOffset[id] = findFit(cr.locs);
		sizeToFit(at+cr.size);
		for (int i=0; i<cr.locs.length; i++) {
			int offset = at+cr.locs[i];
			assert(0 == yyCheck[offset]);
			yyTable[offset] = cr.acts[i];
			yyCheck[offset] = id;
		}
	}
	private void sizeToFit(int i) {
		if (size<i) {
			size = i;
			yyCheck = grow(yyCheck);
			yyTable = grow(yyTable);
		}
	}
	private int[] grow(int[] a) {
		int[] b = new int[size];
		for (int i=0; i<a.length; i++) b[i] = a[i];
		return b;
	}
	private int findFit(int[] locs) {
		int offset = 0;
		while (offset < size) {
			if (testFit(offset, locs)) break;
			else offset++;
		}
		return offset;
	}
	private boolean testFit(int offset, int[] locs) {
		for (int i:locs) {
			if (offset+i >= size) return true;
			if (yyCheck[offset+i] != 0) return false;
		}
		return true;
	}
	private static int defaultReduce(Integer[] row) {
		// Produce a histogram for the reductions in the row.
		int[] h = new int[1-min(row)];
		for (Integer i:row) {
			if (i==null) continue;
			if (i<0) h[-i]++;
		}
		return 0-maxPosn(h);
	}
	private static int defaultGoto(Integer[] col) {
		int[] h = new int[col.length];
		for (Integer i:col) {
			if (i==null) continue;
			if (i>0) h[i]++;
		}
		return maxPosn(h);
	}
	private static int min(Integer[] row) {
		int k=0;
		for (Integer i:row) {
			if (i==null) continue;
			if (i<k) k=i;
		}			
		return k;
	}
	/**
	 * 
	 * @param h an array of non-negative integers
	 * @return the index to the greatest of h (or the first such, in a tie).
	 */
	private static int maxPosn(int[] h) {
		int win=0, winpos=0;
		for (int i=0; i<h.length; i++) {
			if (h[i]>win) { win = h[i]; winpos = i; }
		}
		return winpos;
	}
	public void writeCode(JavaClass cw) {
		cw.code("	private static final int[] yyTable = ");
		cw.code(yyTable);
		cw.codeln(";");
		cw.code("	private static final int[] yyCheck = ");
		cw.code(yyCheck);
		cw.codeln(";");
		cw.code("	private static final int[] yyOffset = ");
		cw.code(yyOffset);
		cw.codeln(";");
		cw.code("	private static final int[] yyDefault = ");
		cw.code(yyDefault);
		cw.codeln(";");
		cw.codeln("	private int yyAct(int type) {");
		cw.codeln("		int offset = yyOffset[yyq] + type;");
		cw.codeln("		return yyCheck[offset]==yyq ? yyTable[offset] : yyDefault[yyq];");
		cw.codeln("	}");
		cw.codeln("	private int yyGo(int type) {");
		cw.codeln("		int eid="+stateCount+"+type, offset = yyOffset[eid] + yyq;");
		cw.codeln("		return yyCheck[offset]==eid ? yyTable[offset] : yyDefault[eid];");
		cw.codeln("	}");
	}
}
